package j2024.j202409;

import java.util.ArrayList;
import java.util.Arrays;

public class j0911 {
    /**
     * 991. 坏了的计算器
     * 在显示着数字 startValue 的坏计算器上，我们可以执行以下两种操作：
     *
     * 双倍（Double）：将显示屏上的数字乘 2；
     * 递减（Decrement）：将显示屏上的数字减 1 。
     * 给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操作数。
     * @param startValue
     * @param target
     * @return
     */
    public static int brokenCalc(int startValue, int target) {
        if(target<startValue){
            return startValue-target;
        }
        int count = 0;
        while(target!=startValue){
            if(target%2==0 && target>startValue){
                count++;
                target/=2;
            }else {
                target++;
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        brokenCalc(5,8);
    }

    /**
     * 56. 合并区间
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
     * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->{
            return a[0]-b[0];
        });
        int n = intervals.length;
        int left = intervals[0][0],right = intervals[0][1];
        ArrayList<int[]> ret = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            int a = intervals[i][0],b = intervals[i][1];
            if(right>=a){
                right = Math.max(right,b);
            }else {
                ret.add(new int[]{left,right});
                left = a;right = b;
            }
        }
        ret.add(new int[]{left,right});
        return ret.toArray(new int[0][]);
    }

    /**
     * 435. 无重叠区间
     * 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。
     * 返回 需要移除区间的最小数量，使剩余区间互不重叠 。
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(v1,v2)->{
            return v1[0]-v2[0];
        });
        int ret = 0;
        int right = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            int a = intervals[i][0],b = intervals[i][1];
            if(a<right){
                ret++;
                right = Math.min(b,right);
            }else {
                right = b;
            }
        }
        return ret;
    }

    /**
     * 452. 用最少数量的箭引爆气球
     * 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。
     * 你不知道气球的确切 y 坐标。
     *
     * 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。
     * 在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。
     * 可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
     *
     * 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
     * @param points
     * @return
     */
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,(v1,v2)->{
            return v1[0]>v2[0]?1:-1;
        });
        int right = points[0][1];
        int ret = 1;
        for (int i = 1; i < points.length; i++) {
            int a = points[i][0],b = points[i][1];
            if(a<=right){
                right = Math.min(right,b);
            }else {
                ret++;
                right = b;
            }
        }
        return ret;
    }
}
